#include <iostream>
#include <vector>
using namespace std;

// DFS 函数，寻找从 start 到 end 的所有路径
void dfs(int start, int end, const vector<vector<int>>& roadlength, vector<bool>& visited, vector<int>& current_path, vector<vector<int>>& all_paths) {
    visited[start] = true; // 标记当前节点为已访问
    current_path.push_back(start); // 将当前节点加入路径

    if (start == end) {
        all_paths.push_back(current_path); // 找到一条路径，保存到 all_paths 中
    } else {
        // 遍历所有邻接节点
        for (int i = 0; i < roadlength.size(); i++) {
            if (roadlength[start][i] != INT_MAX && !visited[i]) { // 如果道路存在且未访问
                dfs(i, end, roadlength, visited, current_path, all_paths); // 递归搜索
            }
        }
    }

    // 回溯
    current_path.pop_back();
    visited[start] = false;
}

int main() {
    int N, M;
    cin >> N >> M;

    // 动态分配二维数组
    vector<vector<int>> roadlength(N, vector<int>(N, INT_MAX)); // 存储道路长度
    vector<vector<int>> restrictions(N, vector<int>(N)); // 存储道路的流量限制（读取但不使用）
    vector<vector<int>> cars(M, vector<int>(2)); // 存储每辆车的起点和终点

    // 读取道路长度
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> roadlength[i][j];
            if (roadlength[i][j] == 0 && i != j) {
                roadlength[i][j] = INT_MAX; // 如果道路长度为 0，则距离为无穷大
            }
        }
    }

    // 读取道路的流量限制（读取但不使用）
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> restrictions[i][j];
        }
    }

    // 读取每辆车的起点和终点
    for (int i = 0; i < M; i++) {
        cin >> cars[i][0] >> cars[i][1];
        cars[i][0]--; // 将输入的起点和终点转换为从 0 开始的索引
        cars[i][1]--;
    }

    // 存储每辆车的所有路径
    vector<vector<vector<int>>> all_cars_paths(M); // 每辆车的所有路径

    // 为每辆车找到所有路径
    for (int i = 0; i < M; i++) {
        int start = cars[i][0];
        int end = cars[i][1];
        vector<bool> visited(N, false); // 记录节点是否被访问
        vector<int> current_path; // 记录当前路径
        vector<vector<int>> all_paths; // 存储所有路径

        dfs(start, end, roadlength, visited, current_path, all_paths);

        all_cars_paths[i] = all_paths; // 保存当前车辆的所有路径
    }

    // 统一打印每辆车的第一个路径
    for (int i = 0; i < M; i++) {
        if (!all_cars_paths[i].empty()) {
            cout << "Car " << i + 1 << " path: ";
            for (int node : all_cars_paths[i][0]) {
                cout << node + 1 << " "; // 输出路径中的节点
            }

            // 计算路径总长度
            int total_length = 0;
            for (int j = 1; j < all_cars_paths[i][0].size(); j++) {
                int u = all_cars_paths[i][0][j - 1];
                int v = all_cars_paths[i][0][j];
                total_length += roadlength[u][v];
            }
            cout << "| Total length: " << total_length << endl;
        } else {
            cout << "Car " << i + 1 << " no path found!" << endl;
        }
    }

    return 0;
}